package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:最大连续1的个数 III
 *
 * 给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
 *
 * 示例 1：
 * 输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
 * 输出：6
 * 解释：[1,1,1,0,0,1,1,1,1,1,1]
 * 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
 *
 * 示例 2：
 * 输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
 * 输出：10
 * 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
 * 粗体数字从 0 翻转到 1，最长的子数组长度为 10。
 *
 * 提示：
 * 1 <= nums.length <= 105
 * nums[i] 不是 0 就是 1
 * 0 <= k <= nums.length
 *
 * author: Mr.Du
 * Date: 2023/12/6
 * Time: 19:24
 */
public class LongestOnes {

    /**
     * 寻找长度最长的子数组，该子数组中的0和1的个数之差不超过k。
     *
     * @param nums 整数数组，只包含0和1。
     * @param k 允许的0和1个数之差的绝对值。
     * @return 返回最长子数组的长度。
     */
    public int longestOnes(int[] nums, int k) {
        int left = 0, right = 0, len = nums.length, res = 0;
        // 遍历数组，使用滑动窗口技巧来寻找符合条件的最长子数组
        while (right < len) {
            res += nums[right++]; // 窗口右边扩展，将新元素的值加到结果中
            // 如果窗口大小超过了结果加上允许的差值k，则需要收缩窗口
            if(right - left > res + k){
                res -= nums[left++]; // 窗口左边收缩，移除最早加入窗口的元素
            }

        }
        // 返回窗口的长度，即为找到的最长子数组的长度
        return len - left;
    }

    public int longestOnes1(int[] nums, int k) {
        int left = 0, right = 0, len = nums.length, count = 0, res = 0;
        while (right < len) {
            if(nums[right] == 1){
                count++;
            }
            right++;
            while(right - left - count > k){
                if(nums[left] == 1){
                    count--;
                }
                left++;
            }
            res = Math.max(res, right - left);
        }
        return res;
    }

    public int longestOnes2(int[] nums, int k) {
        int n = nums.length;
        int l = 0, r = 0;
        int res = 0, cnt = 0;
        while(r < n){
            if(nums[r] == 0) cnt++;
            while(cnt > k){
                if(nums[l] == 0) cnt--;
                l++;
            }
            r++;
            res = Math.max(res, r - l);
        }
        return res;
    }

    public static void main(String[] args) {
        LongestOnes longestOnes = new LongestOnes();
        int[] nums = {0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
        int res = longestOnes.longestOnes1(nums, 3);
        System.out.println(res);
    }
}
